package sword.offer;

import sword.offer.common.TreeNode;

/**
 * 输入一棵二叉树的根节点，判断该树是不是平衡二叉树。
 * 如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class FiftyFiveII {
    class Solution {
        int max = 1;
        public boolean isBalanced(TreeNode root) {
            dfs(root,0);
            return root == null || max == 1;
        }

        private int dfs(TreeNode root, int level){
            if(root == null ){
                return level;
            }
            int lh = dfs(root.left,level+1);
            int lr = dfs(root.right, level+1);
            max = Math.max(max, Math.abs(lh-lr));
            return Math.max(lh, lr);
        }
    }
}
